package recursion

import problem.Problem

import scala.collection.mutable

class Q509FibonacciNumber extends Problem {
  def fib(N: Int): Int = {
    val cache = mutable.Buffer[Int](0, 1)
    f(N, cache)
  }

  def f(n: Int, cache: mutable.Buffer[Int]): Int = {
    if (n < cache.size) cache(n)
    else {
      val r = f(n - 1, cache) + f(n - 2, cache)
      cache.append(r)
      r
    }
  }

  def fib2(N: Int): Int = {
    if (N == 0) 0
    else if (N == 1) 1
    else {
      var a = 0
      var b = 1
      (2 to N).foldLeft((0, 1)) { case ((n_2, n_1), _) =>
        (n_1, n_2 + n_1)
      }._2
    }
  }

  override def test(): Unit = {
    fib(0) shouldBe (0)
    fib(1) shouldBe (1)
    fib(2) shouldBe (1)
    fib(3) shouldBe (2)
    fib(4) shouldBe (3)
    fib2(4) shouldBe (3)
  }
}